package main

func lastRemaining(n int) int{
	head :=1
	steps :=1
	//left=true表示从左边开始，left=false从右边开始
	left :=true
	for n >1{
		//从左边开始移除or（从右边开始移除，数列总数为奇数）
		if left || n % 2!=0{
			head +=steps
		}
		//步长*2 位运算 1 -> 10(2) ->100(4) ->1000(8)
		steps <<=1
		//总数不断除以2
		n >>=1
		//取反移除方向
		left =!left
	}
	return head
}
